package leetcode.Hot100;

import java.util.*;

/**
 * @author Cheng Jun Description: 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 * @version 1.0
 * @date 2021/11/5 14:01
 */
public class lengthOfLongestSubstring {

    public static void main(String[] args) {
        lengthOfLongestSubstring2("aab");
        lengthOfLongestSubstring0("pwwkew");
    }

    static int lengthOfLongestSubstring0(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int i = -1, res = 0;
        for (int j = 0; j < s.length(); j++) {
            if (dic.containsKey(s.charAt(j)))
                // 发生重复位置前的所有下标不可用
                i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
            dic.put(s.charAt(j), j); // 哈希表记录
            res = Math.max(res, j - i); // 更新结果
        }
        return res;
    }

    // 依次往后遍历，发生重复后，从前面的那个重复元素后一个元素开始再次遍历，并且比较最大子串长度
    @Deprecated
    static int lengthOfLongestSubstring(String s) {
        int longestLength = 0;
        if (s.length() == 0) return longestLength;
        HashMap<Character, Integer> charMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char curChar = s.charAt(i);
            // 如果不存在，就存进去, 并且更新 longestLength
            if (!charMap.containsKey(curChar)) {
                charMap.put(curChar, i);
                longestLength = Math.max(charMap.size(), longestLength);
            } else {
                // i 重置为 发生重复元素（重复元素取前面那个）的后一个元素下标
                // 清空 charMap,
                i = charMap.get(curChar);
                charMap.clear();
            }
        }
        return longestLength;
    }

    // LinkedHashMap 依次循环 s.toCharArray 然后某个重复值后，移除重复值前面所有的数据包括重复值，然后再插入重复值
    @Deprecated
    static int lengthOfLongestSubstring1(String s) {
        int length = 0;
        LinkedHashMap<Character, Integer> charMap = new LinkedHashMap<>(s.length());
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (charMap.containsKey(chars[i])) {
                outer:
                while (!charMap.isEmpty()) {
                    Iterator<Character> iterator = charMap.keySet().iterator();
                    while (iterator.hasNext()) {
                        Character next = iterator.next();
                        iterator.remove();
                        if (next == chars[i]) {
                            break outer;
                        }
                    }
                }
            }
            charMap.put(chars[i], i);
            length = Math.max(length, charMap.size());
        }
        return length;
    }

    // 暂时看不懂
    static int lengthOfLongestSubstring2(String s) {
        // 记录字符上一次出现的位置
        int[] last = new int[128];
        Arrays.fill(last, -1);
        int length = s.length();
        int res = 0;
        int start = 0;
        for (int i = 0; i < length; i++) {
            int index = s.charAt(i);
            int count = last[index] + 1;
            // 记录起始位置
            start = Math.max(start, count);
            res = Math.max(res, i - start + 1);
            last[index] = i;
        }
        return res;
    }
}
